#include <iostream>
#include "SparseGraph.h"
#include "ReadGraph.h"
#include "Components.h"
#include "Path.h"
#include "ShortestPath.h"
#include "DenseGraph.h"

using namespace std;
int main() {

//    string filename1="testG1.txt";
//    SparseGraph g1 = SparseGraph(13, false);
//    ReadGraph<SparseGraph>(g1, filename1);
//    Component<SparseGraph> component1(g1);
//    cout << "testG1.txt, Component count " << component1.count() << endl;
//    component1.isConnected(10,12)?
//        cout<<"is connected":cout<<"is not connected";
//
//    cout<<endl;
//
//    string filename2="testG2.txt";
//    SparseGraph g2=SparseGraph(7, false);
//    ReadGraph<SparseGraph>(g2,filename2);
//    Component<SparseGraph> component2(g2);
//    cout<<"testG2.txt,Component count "<<component2.count()<<endl;
//    component2.isConnected(1,3)?
//    cout<<"is connected":cout<<"is not connected";
//
//    cout<<endl;
//
//    string filename="textG";
//    SparseGraph g=SparseGraph(7,false);
//    ReadGraph<SparseGraph>(g,filename);
//    DenseGraph d=DenseGraph(7, false);
//    ReadGraph<DenseGraph>(d,filename);
//    g.show();
//    d.show();
//    cout<<endl;
//
//    Path<SparseGraph> dfs(g,0);
//    cout<<"dfs : ";
//    dfs.showPath(6);
//
//    ShortestPath<DenseGraph> bfs(d,0);
//    cout<<"bfs : ";
//    bfs.showPath(6);
//    cout<<endl;
//    cout<<"length: ";
//    cout<<bfs.length(6);

    string filename="oula";
    SparseGraph g = SparseGraph(8, false);
    ReadGraph<SparseGraph>(g, filename);
    g.show();
    ShortestPath<SparseGraph> bfs(g,0);
    bfs.showPath(7);

    return 0;
}
//
//#include <iostream>
//#include <stdio.h>
//using namespace std;
//const int maxv = 100 + 2;
//int odds[maxv];                 /* 顶点 */
//int du[maxv];                   /* 每个顶点的度数 */
//int p[maxv];                    /* 并查集数组 */
//bool used[maxv];
//int scc[maxv];                  /* scc个数 */
//void init(int n)                /*初始化数组*/
//{
//    for(int i = 0; i <= n; ++i)
//    {
//        odds[i] = 0;
//        p[i] = -1;
//        du[i] = 0;
//        used[i] = 0;
//    }
//}
//int utf_find(int x)     /*本函数用来寻找结点x的代表结点。如果x尚未加入到数组当中或者x即 */
//{                       /* 为自己以及其他结点的代表结点，p[x]<0. 此时返 回自己x；*/
//    if(0 <= p[x])       /*若结点x已被加入到集合A中且此时x的代表结点不是自己*/
//    {                   /* 则递归调用寻找所在连通图的代表结点x',特征是p[x']<0。*/
//        p[x] = utf_find(p[x]);
//        return p[x];
//    }
//    return x;
//}
//void utf_union(int a, int b)  //当加入一条边的时候，是合并两个连通图。
//{
//    int r1 = utf_find(a);     //寻找新加入边的两个结点所在连通图的代表结点是否一样，
//    int r2 = utf_find(b);     //一样的话则为“冗余边”；否则即是将两个连通图连通在一块。
//    if(r1 == r2)
//        return;
//    int n1 = p[r1];           //每个连通图中结点的个数，连通图A1中的结点个数为|n1|，连通图A2中的结点个数为|n2|.
//    int n2 = p[r2];
//    if(n1 < n2)               //A1中结点个数大于A2中结点个数
//    {                         //<span style="font-family:Arial, Helvetica, sans-serif;">将A2中的代表结点，再链接到A1中的代表结点。</span>
//        p[r2] = r1;           //这样A1，A2中结点的代表结点将都是A1的代表结点。
//        p[r1] += n2;          //实现两个连通图的合并.更新新的连通图A1中的结点个数。
//    }
//    else
//    {
//        p[r1] = r2;           //同上。
//        p[r2] += n1;
//    }
//}
//int main()
//{
//    int n = 0;
//    int m = 0;
//    int a = 0;
//    int b = 0;
//    int i = 0;
//    int cnt = 0;
//    while(scanf("%d%d", &n, &m) != EOF)
//    {
//        init(n);
//        cnt = 0;
//        for(i = 1; i <= m; ++i)        //本段为加入边，并对边做并查集归并。具体如上所示。
//        {
//            scanf("%d%d", &a, &b);
//            du[a]++;
//            du[b]++;
//            utf_union(a, b);
//        }
//        for(i = 1; i <= n; ++i)
//        {
//            int f = utf_find(i);
//            if(!used[f])              //检查图中的连通图个数
//            {
//                used[f] = 1;
//                scc[cnt++] = f;
//            }
//            if(1 == du[i]%2)          //检查每个连通图中度数为奇数的结点个数
//                odds[f]++;
//        }
//        int ret = 0;
//        for(i = 0; i < cnt; ++i)      //对每个连通图做判断
//        {
//            if(0 == du[scc[i]])       //如果连通图是单个结点，则继续。
//                continue;
//            if(0 == odds[scc[i]])     //否则如果连通图中度数为为奇数的结点个数为0，则只需
//                ++ret;                //一笔或者或者只需一条路径就能遍历所有的边
//            else                      //若连通图中度数为奇数的节点个数不为0，
//                ret += odds[scc[i]]/2;//<span style="font-family:Arial, Helvetica, sans-serif;">设为2k，则需要k条路径才能遍历所有的边。</span>
//        }
//        printf("%d\n", ret);          //函数最后返回遍历所有的边需要的路径数
//    }
//    return 0;
//}
